from itertools import chain, combinations

# --------------------------------------------------------------------------------------- 基本的频繁集算法
def powerset(s):
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s) + 1))

'''
这个naive_frequent_itemsets算法的目的是找到所有可能的项集的子集，并计算其在交易数据集中的支持度。
它并不是找到所有的排列（Permutation），而是找到所有的组合（Combination）。

这里使用的powerset函数生成一个给定集合的所有非空子集。
例如，如果给定集合是{A, B}，则它的幂集（不包括空集）是{A}, {B}, {A, B}。
这些子集用于检查它们在事务数据集中的出现频率。

因此，这个算法会遍历所有可能的项集组合，
对每一个计算支持度，并检查是否满足最小支持度要求。
这样做非常耗时，尤其是当项集很大时。这也是为什么在实践中通常使用如Apriori这样的更高效算法。

'''

def naive_frequent_itemsets(transactions, min_support):
    all_items = set(chain.from_iterable(transactions))
    freq_itemsets = {}
    
    for itemset in powerset(all_items):
        support = sum(1 for transaction in transactions if set(itemset).issubset(transaction))
        if support >= min_support:
            freq_itemsets[itemset] = support
            
    return freq_itemsets







'''
Apriori算法的核心思想是通过逐级构建频繁项集来减少需要检查的项集数量，从而提高算法效率。
这一思想基于一个先验原理：任何非频繁（不满足最小支持度要求的）项集的所有超集也一定是非频繁的。
'''
# --------------------------------------------------------------------------------------- apriori频繁集算法
def apriori_frequent_itemsets(transactions, min_support):
    # -----------------------------------------------------------------首先找到单货物的出现频率
    single_item_counts = {}
    for transaction in transactions:
        for item in transaction:
            if item in single_item_counts:
                single_item_counts[item] += 1
            else:
                single_item_counts[item] = 1
    # -----------------------------------------------------------------找到单货物的超过min_support的集合
    freq_single_items = {item for item, count in single_item_counts.items() if count >= min_support}
    freq_itemsets = {}
    
    k = 1
    current_level = [frozenset([item]) for item in freq_single_items]       # 使用frozenset（python不可变集合）
    
    
    while current_level:
        next_level = []
        level_counts = {}
        
        for transaction in transactions:
            for candidate in current_level:                 # 循环找到的频繁集
                if candidate.issubset(transaction):         # 这个candidate属于transaction的子集
                    if candidate in level_counts:
                        level_counts[candidate] += 1
                    else:
                        level_counts[candidate] = 1
                        
        for candidate, count in level_counts.items():
            if count >= min_support:
                freq_itemsets[candidate] = count            # 只保留频繁集
        
                
        # 生成下一级候选项集
        unique_items = set()
        for candidate in current_level:
            unique_items.update(candidate)

        print(f'\n\n循环层级{k}...\ncurrent_level:{current_level}...\nfreq_itemsets:{freq_itemsets}...\nunique_items:{unique_items}..........')
        
        next_level = [frozenset(x) for x in combinations(unique_items, k+1) if all(frozenset(s) in current_level for s in combinations(x, k))]
        
        current_level = next_level
        k += 1

    return freq_itemsets



# 使用示例
transactions = [
    {'A', 'B', 'C'},
    {'A', 'B','D'},
    {'B', 'C','D'},
    {'A', 'C','D'},
    {'A', 'C'},
    {'C', 'D'},
    {'B', 'D'}
]
min_support = 1

if __name__=='__main__':
    print(naive_frequent_itemsets(transactions, min_support))
    print(apriori_frequent_itemsets(transactions, min_support))